#include "func.h"

#define N 10
#define swap(a,b) {int temp;temp=a;a=b;b=temp;}

void adjust_max_heap(int arr[],int adjust_pos,int arr_len)
{
    int dad=adjust_pos;//调整的位置作为父亲
    int son=2*dad+1;//左孩子
    while(son<arr_len)
    {
        //son记录较大的孩子
        if(son+1<arr_len&&arr[son]<arr[son+1])
        {
            son++;
        }
        if(arr[son]>arr[dad])
        {
            swap(arr[son],arr[dad]);
            //孩子作为父亲，通过while继续向下调整
            dad=son;
            son=2*dad+1;
        }else{
            break;
        }
    }
}

void arr_heap(int arr[])
{
    int i;
    for(i=N/2-1;i>=0;i--)
    {
        adjust_max_heap(arr,i,N);
    }
    swap(arr[0],arr[N-1]);
    for(i=N-1;i>1;i--)
    {
        adjust_max_heap(arr,0,i);
        swap(arr[0],arr[i-1]);
    }
}


int main()
{
    //生成随机数，并存储在a[i]中
    srand(time(NULL));
    int i,j,a[100];
    for(i=0;i<N;i++)
    {
        a[i]=rand()%100;
    }

    //打印
    for(i=0;i<N;i++)
    {
        printf("%-3d",a[i]);
    }
    printf("\n");

    //堆排
    arr_heap(a);
    //打印
    for(i=0;i<N;i++)
    {
        printf("%-3d",a[i]);
    }
    printf("\n");

    return 0;
}